#include <stdio.h>
#include <stdlib.h>


void merge(int arr[],int left, int mid,int right) {
	
	int *L=(int *)malloc(mid - left+1 * sizeof(int));
	int *R=(int*)malloc(right - mid * sizeof(int));

	//?????????????
	for (int i= left;left<=mid;left++) {
		L[i] = arr[i];
	}
	for (int i = mid + 1;i<=right;i++) {
		R[i] = arr[i];
	}
	int l = sizeof(L) / sizeof(L[0]);
	int r = sizeof(R) / sizeof(R[0]);
	int ll = 0;
	int rr = 0;
	int arrl = left;
	//????????????
	while (ll < l && rr < r) {
		if (L[ll] < R[rr]) {
			arr[arrl] = L[ll];
			ll++;
		}
		else {
			arr[arrl] = R[rr];
			rr++;
		}
		arrl++;
	}

	if (l<=ll) {
		while (r>rr) {
			arr[arrl] = R[rr];
			rr++;
			arrl++;
		}
	}
	else {
		while (l>ll) {
			arr[arrl] = L[ll];
			ll++;
			arrl++;

		}
	}
	free(L);
	free(R);
}

void mergesort(int arr[],int left,int right) {
	while (right >left) {
		int mid = (right + left) / 2;

		mergesort(arr, left, mid);
		mergesort(arr, mid + 1, right);
		merge(arr, left, mid, right);
	}
}

int main() {
	int arr[9] = {7,6,8,3,1,5,2,4,9};
	int result[9];
	int n = sizeof(arr) / sizeof(arr[0]);
	mergesort(arr,0,n-1);



	for (int i = 0;i<n;i++) {
		printf("%d \t",arr[i]);
	}
}